﻿// 1002train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

/*
 老李的货车额定载货重量为wt。
现有两种货物，货物A单件重量为wa，单件运费利润为pa
货物B单件重量为wb，单件运费利润为pb
老李每次发车时载货总重量刚好为货车额定载货重量wt，
车上必须同时有货物A和货物B，货物A、B 不可切割。
老李单车次满载运输可获得的最高利润是多少？
输入描述
输入一行五个正整数。
第一个数字为货物A的单件重量wa，0<wa<10000
第二个数字为货物B的单件重量wb，0<wb<10000
第三个数字为货车的额定载重wt，0<wt<100000
第四个数字为货物A的单件运费利润pa，0<pa<1000
第五个数字为货物B的单件运费利润pb，0<pb<1000
输出描述
单次满载运输的最高利润


输入
10 8 36 15 7
输出
44
运送2个A货物，2个B货物
 */
class Solution01
{
public:
    Solution01(int wa, int wb, int total_w, int pa, int pb)
    {
        int limit_a = total_w / wa;

        int result = 0;
        for (int count_a=1; count_a <=limit_a; count_a++)
        {
            int curr_res = 0;
            int count_b = (total_w - count_a * wa)/wb;
            if (count_b == 0)
            {
	            //至少1个b货物
                continue;
            }

            curr_res = count_a * pa + count_b * pb;

            result = max(curr_res, result);
	        //for---
        }
        cout << result;
        
	    //Solution01
    }
};


/*
第一条评论是"hello,2,ok,0,bye,0"，第二条评论是"test,0"，第三条评论是"one,1,two,1,a,0"。
所有评论被保存成"hello,2,ok,0,bye,0,test,0,one,1,two,1,a,0"。

对于上述格式的评论，请以另外一种格式打印：
- 首先打印评论嵌套的最大深度。
- 然后是打印n行，第i (1 ≤ i ≤ n) 行对应于嵌套级别为i 的评论 (根评论的嵌套级别为1)。
- 对于第i行，嵌套级别为的评论按照它们出现的顺序打印，用空格分隔开。
输入描述
一行评论。由英文字母、数字和英文逗号组成。
保证每个评论都是由英文字符组成的非空字符串。每个评论的数量都是整数(至少由一个数字组成)整个字符串的长度不超过10^6.
给定的评论结构保证是合法的

输出描述
按照给定的格式打印评论。对于每一级嵌套，评论应该按照输入中的顺序打印。

输入
hello,2,ok,0,bye,0,test,0,one,1,two,1,a,0
输出
3
hello test one
ok bye two
a
如题目描述中图所示，最大嵌套级别为3，嵌套级别为1的评论是"hello test one"，
嵌套级别为2的评论是"ok bye two"，嵌套级别为3的评论为"a"
A,3,B,2,C,0,D,1,E,0,F,1,G,0,H,1,I,1,J,0,K,1,L,0,M,2,N,0,O,1,P,0
 */
class Solution02
{
public:
    void backTrack(
        vector<string>& str_vec,
		int index,
        int layer
    )
    {
        if (result.size()==layer)
        {
            result.push_back({ str_vec[index] });
        }
        else
        {
            result[layer].push_back(str_vec[index]);
        }

        //A,3,B,2,C,0,D,1
        int count = stoi(str_vec[index + 1]);
        for (int i=0;i<count; i++)
        {
            index += 2;
            while (cache.count(index)>0)
            {
                index += 2;
            }
            cache.insert(index);
            backTrack(str_vec, index, layer + 1);
        }

	    //backTrack
    }

    Solution02(vector<string>&str_vec)
    {
        int v_size = str_vec.size();
        for (int i=0; i< v_size; i+=2)
        {
            if (cache.count(i) > 0) continue;
            cache.insert(i);
            backTrack(str_vec, i, 0);
	        //for---
        }

        int result_size = result.size();
        cout << result_size << '\n';
        for (int layer=0; layer< result_size; layer++)
        {
            int item_size = result[layer].size();
            for (int i=0;i< item_size; i++)
            {
                cout << result[layer][i];
	            if (i!=item_size-1)
	            {
                    cout << ' ';
	            }
            }

            if (layer!=result_size-1)
            {
                cout << '\n';
            }
	        //for---
        }

	    //Solution02
    }
private:
    unordered_set<int>cache;
    vector<vector<string>>result;
};

/*
 快递公司每日早晨，给每位快递员推送 需要送到客户手中的快递以及路线信息，
 快递员自己又查找了一些客户与客户之间的路线距离信息，
 请你依据这些信息，给快递员设计一条最例短路径，告诉他最短路径的距离。注意：
1. 不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中
2. 用例保证一定存在投递站到每位客户之间的路线，
但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过。
3. 所有快递送完后，快递员还需要回到投递站

输入描述
首行输入两个正整数n，m。
接下来n行，输入快递公司发布的客户快递信息，
格式为：客户id 投递站到客户之间的距离distance
再接下来的m行，是快递员自行查找的客户与客户之间的距离信息格式为：
客户1id 客户2id distance
在每行数据中，数据与数据之间均以单个空格分割。
规格：
0<n <=10
0 <= m <= 10
0<客户id <= 1000
0< distance <= 10000
输出描述
最短路径距离，如无法找到，请输出 -1
示例1：
输入：
2 1
1 1000
2 1200
1 2 300
输出：
2500
说明：
路径1:快递员先把快递送到客户1手中，接下来直接走客户1到客户2之间的直通路线，
最后走投递站与客户2之间的路，回到投递站，距离为1000 + 300 + 1200 = 2500
路径2: 快递员先把快递送到客户1手中，接下来回快递站，
再出发把客户2的快递送到，在返回到快递站，距离为：1000 + 1000 + 1200 + 1200 = 4400
路径3:快递员先把快递送到客户2手中，
接下来直接走客户2到客户1之间的直通路线，
最后走投递站和客户1之间的路，回到投递站，距离为1200 + 300 + 1000 =2500
所有路径中，最短路径距离为2500
示例2：
输入：
5 1
5 1000
9 1200
17 300
132 700
500 2300
5 9 400
输出：
9200
说明：在所有可行的路径中，最短路径长度为
1000 + 400 + 1200 + 300 + 300 + 700 + 700 + 2300 + 2300 = 9200
*/
class Solution03
{
public:
    struct Node
    {
        int status, index;
        Node() = default;
        Node(int status, int index) :status(status), index(index) {};
    };
    Solution03(vector<vector<int>>&link_vec)
    {
        //统计节点个数
        id_map[0] = 0; //id0 对应的index为0
    	int link_v_size = link_vec.size();
        int real_i = 1; 
        for (int i=0 ;i< link_v_size; i++)
        {
            //item item[0]表示0 item[1]为站点的索引
            vector<int>item = link_vec[i];
            if (id_map.count(item[1])==0)
            {
                id_map[item[1]] = real_i;
                real_i++;
            }
	        //for---
        }
        int N = id_map.size();

        cost_grid = vector<vector<int>>(N, vector<int>(N, INT_MAX));
        status_grid = vector<vector<int>>(1024, vector<int>(N, INT_MAX));

        //统计每个节点开销
        for (int i=0; i<link_v_size; i++)
        {
            vector<int>item = link_vec[i];
            int index_1 = id_map.at(item[0]);
            int index_2 = id_map.at(item[1]);
            int val = item[2];
            cost_grid[index_1][index_2] = val;
            cost_grid[index_2][index_1] = val;
        }
            


        deque<Node>bfs_queue;
        //第一个0表示未访问过任何，第二个0表示起点
        bfs_queue.push_back(Node(0,0));
        status_grid[0][0] = 0;

        while (!bfs_queue.empty())
        {
            Node top_node = bfs_queue.front();
            bfs_queue.pop_front();
            int top_status = top_node.status;
            int top_i = top_node.index;

            //遍历全部节点
            for (int next=0; next <N; next++)
            {
                
                if (next == top_i || cost_grid[top_i][next] == INT_MAX)
                    continue;

                int new_status = top_status;
                if (next >0)
                {
                    new_status = top_status | int(pow(2, next - 1));
                }

                int curr_cost = cost_grid[top_i][next] + status_grid[top_status][top_i];

                if (curr_cost<status_grid[new_status][next])
                {
                    status_grid[new_status][next] = curr_cost;
                    bfs_queue.push_back(Node(new_status, next));
                }
                //for---
            }

	        //while---
        }

        int final_status = pow(2, N-1) - 1;
        if (status_grid[final_status][0]==INT_MAX)
        {
            cout << -1;
            return;
        }
        cout << status_grid[final_status][0];
	    //Solution03
    }
private:
    vector<vector<int>>status_grid;
    vector<vector<int>>cost_grid;
    unordered_map<int, int>id_map;//id对应的索引
};


/*
 一个局域网内有很多台电脑，分别标注为0到N-1的数字。
相连接的电脑距离不一样，所以感染时间不一样，感染时间用t表示。
其中网络内一个电脑被病毒感染，其感染网络内所有的电脑需要最少需要多长时间。如果最后有电脑不会感染，则返回-1。
给定一个数组times表示一个电脑把相邻电脑感染所用的时间。
path[]= {i,j,t} 表示电脑i->j电脑i上的病毒感染j，需要时间t。


输入描述
第一行一个参数，表示局域网内电脑个数N。1<=N<=200
第二行一个参数，表示网络连接条数M
接下来M行，表示网络连接情况，格式为i j t
最后一行一个参数，表示病毒最开始所在的电脑编号


输出描述
一个数字，表示感染电脑所需要花费的所有时间。

输入
4
3
2 1 1
2 3 1
3 4 1
2
输出
2
 */
class Solution04
{
public:
    struct Node
    {
        int index, val;
        Node() = default;
        Node(int index, int val) :index(index), val(val) {};
    };
    Solution04(int N, vector<vector<int>>&link_v,int start_i)
    {
        cost_grid = vector<vector<int>>(N, vector<int>(N,INT_MAX));
        status_grid = vector<int>(N, INT_MAX);

        int link_v_size = link_v.size();
        for (int i=0; i<link_v_size; i++)
        {
            vector<int>item = link_v[i];
            int start_i = item[0] - 1;
            int end_i = item[1] - 1;
            int val = item[2];

            cost_grid[start_i][end_i] = val;
	        //for---
        }

        deque<Node>bfs_queue;
        //开头节点开销为0
        bfs_queue.push_back(Node(start_i, 0));
        status_grid[start_i] = 0;

        while (!bfs_queue.empty())
        {
            Node top_node = bfs_queue.front();
            bfs_queue.pop_front();
            int top_i = top_node.index;
            int top_val = top_node.val;

            for (int next=0; next <N; next++)
            {
                if (next == top_i || cost_grid[top_i][next] == INT_MAX)
                    continue;

                int curr_val = top_val + cost_grid[top_i][next];
                if (curr_val<status_grid[next])
                {
                    status_grid[next] = curr_val;
                    bfs_queue.push_back(Node(next, curr_val));
                }
	            //for---
            }

	        //while---
        }

        int result = 0;
        for (auto&cost:status_grid)
        {
            result = max(result, cost);
        }

        if (result==INT_MAX)
        {
            cout << -1;
            return;
        }
        cout << result;
	    //Solution04
    }
private:
    vector<vector<int>>cost_grid;
    vector<int>status_grid;
};


int main()
{
	{
        int N;
        cin >> N;

        int v_size;
        cin >> v_size;

        vector<vector<int>>grid(v_size);
        for (int i=0; i<v_size; i++)
        {
            vector<int>item(3);
            cin >> item[0] >> item[1] >> item[2];
            grid[i] = item;
        }
        int start_i;
        cin >> start_i;

        Solution04 solu(N, grid, start_i - 1);
        return 0;
	}
	{
/*
2 1
1 1000
2 1200
1 2 300
*/
        int size0, size;
        cin >> size0 >> size;

        vector<vector<int>>link_vec;

        for (int i=0; i<size0; i++)
        {
            vector<int>item(3);
            item[0] = 0;
            cin >> item[1] >> item[2];
            link_vec.push_back(item);
        }

        for (int i=0; i<size; i++)
        {
            vector<int>item(3);
            cin >> item[0] >> item[1] >> item[2];
            link_vec.push_back(item);
        }

        Solution03 solu(link_vec);

        return 0;
	}
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        vector<string>str_vec;
        while (getline(oh_sstream, token, ','))
        {
            str_vec.push_back(token);
        }

        Solution02 solu(str_vec);

        return 0;
	}
    int wa, wb, total_w, pa, pb;
    cin >> wa >> wb >> total_w >> pa >> pb;

    Solution01 solu(wa, wb, total_w, pa, pb);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
